package com.qf.day4;

import java.util.Arrays;

public class Demo3 {

    public static void swap(int a,int b) {
        int tmp = a;
        a=b;
        b=tmp;
    }
    public static void swap(int[] arr , int indexA, int indexB){
        int tmp =arr[indexA];
        arr[indexA] = arr[indexB];
        arr[indexB] = tmp;
    }
    /**
     * 冒泡排序 思路 两个比较找大的交换，让最大的放到最后 length-1继续找
     * @param arr 要排序的数组
     */
    public static void bubbleSort(int[] arr) {
        for (int j = 0; j < arr.length-1; j++) { //外层到最后减一
            for (int i = 0; i < arr.length-1-j; i++) { //内层还需要再减j(排序好的就不需要再排序了)
                if(arr[i]>arr[i+1]){
//                    int tmp = arr[i];
//                    arr[i]=arr[i+1];
//                    arr[i+1] = tmp;
                    swap(arr,i,i+1);
                }
            }
        }
    }

    /**
     * 选择排序 思路遍历找maxIndex放到数组最后
     * @param arr 要排序的数组
     */
    public static void selectSort(int[] arr){

        for (int i = 0; i < arr.length; i++) {
            int maxIndex = 0;
            for (int j = 0; j < arr.length-i; j++) {
                if(arr[maxIndex]<arr[j]){
                    maxIndex = j;
                }
            }
            swap(arr, arr.length-1-i, maxIndex); //最大的下标和遍历数组最后一个元素交换
        }
    }

    /**
     * 二分查找 思路下标 min middle max 定位
     * @param arr 要查找的数组
     * @return 返回查找到的下标 没有返回-1
     */
    public static int binarySearch(int[] arr , int n){
        int minIndex = 0;
        int middleIndex = arr.length/2;
        int maxIndex = arr.length;
        while(minIndex<=maxIndex){
            if(arr[middleIndex]<n){
                //中间的元素小于要找的n,将min移过来 中间改变
                minIndex = middleIndex+1;
                middleIndex =maxIndex-minIndex/2;
            } else if (arr[middleIndex]>n) {
                //中间元素大于要找的n，将max移过来 minddle位置改变
                maxIndex = middleIndex-1;
                middleIndex = maxIndex-minIndex/2+minIndex;
            }else {
                //不大不小就相等喽
                return middleIndex;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {2,7,9,10,3,5,1};
        bubbleSort(arr); //冒泡排序
        for (int i : arr) {
            System.out.print (i+" ");
        }
        System.out.println();
        int[] arr2 = {2,7,9,10,3,5,1,11,56,21};
        selectSort(arr2); //选择排序
        for (int i : arr2) {
            System.out.print (i+" ");
        }
        System.out.println();
        int[] arr3 = {99,10,3,5,1,11,56,21};
        Arrays.sort(arr3); // Arrays 提供 sort()方法排序
        for (int i : arr3) {
            System.out.print (i+" ");
        }
        System.out.println();
        //二分查找
        System.out.println(binarySearch(arr2, 11));
    }
}
